package com.uyong.study.algorithm.sort;

/**
 * 快速排序O(nlogn),原地O(1),非稳定
 * 
 * @author gonggy
 * @since 2019-01-29
 */
public class QuickSort implements ISort {

	@Override
	public void sort(int[] data) {
		sort(data, 0, data.length - 1);
	}

	private void sort(int[] data, int begin, int end) {
		if (begin >= end) {
			return;
		}

		// 获取分区点下标
		int pivotIndex = partition(data, begin, end);
		sort(data, begin, pivotIndex - 1);
		sort(data, pivotIndex + 1, end);
	}

	private int partition(int[] data, int begin, int end) {
		int pivot = data[end];// 选择最后一个元素为分区点
		int pivotIndex = begin;
		for (int i = begin; i < end; i++) {
			if (data[i] < pivot) {
				if (i != pivotIndex) {
					int tmp = data[i];
					data[i] = data[pivotIndex];
					data[pivotIndex] = tmp;
				}
				pivotIndex++;
			}
		}
		data[end] = data[pivotIndex];
		data[pivotIndex] = pivot;
		return pivotIndex;
	}
}
